Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Find the Index of the First Occurrence in a String

Problem Statement

Given two strings str1 and str2, return the index of first occurrences of the str2 string in str1. If str2 doesn't exists in str1 string, return -1.

Examples

  • Example 1:

    • Input: str1 = "algorithms", str2 = "rith"
    • Expected Output: 4
    • Justification: The substring "rith" begins at index 4 in the string "algorithms".
  • Example 2:

    • Input: str1 = "openai", str2 = "ai"
    • Expected Output: 4
    • Justification: The substring "ai" starts at index 4 in the string "openai".
  • Example 3:

    • Input: str1 = "challenge", str2 = "test"
    • Expected Output: -1
    • Justification: The substring "test" does not appear in the string "challenge", hence the output is -1.

Solution

To solve this problem, we'll adopt a straightforward search approach. We iterate through the main string (str1) and for each position, we check if the following characters match the target substring (str2).

This method is effective because it directly compares segments of the str1 with the str2, ensuring that no possible starting point is overlooked. The key to this approach's effectiveness lies in its meticulous examination of each potential match point, guaranteeing that as soon as the str2 is found, its starting index is immediately returned, optimizing for both clarity and efficiency.

Step-by-step Algorithm

  • Start by checking if the str2 is empty. If it is, return 0, as an empty string is considered to be found at the beginning.
  • Loop through the str1 string starting from index 0.
    • For each index in the str1, compare the substring that starts at this index and spans the length of the str2 with the str2 itself.
    • If a match is found, return the current index as the starting point of the str2 in the str1.
  • If no match is found by the end of the loop, return -1 to indicate the str2 was not found in the str1.

Algorithm Walkthrough

Using the input str1 = "algorithms", str2 = "rith":

  1. Initialization: We start with str1 = "algorithms" and str2 = "rith". The goal is to find the first occurrence of str2 in str1.

  2. Check for Empty str2: First, check if str2 is empty. Since str2 is not empty, we proceed to the next step.

  3. Start Looping Through str1:

    • We initiate a loop that starts from index 0 of str1 and will go up to str1.length - str2.length to ensure we can compare the full length of str2 without going out of bounds.
  4. Index 0 (i = 0):

    • Compare str1.substring(0, 4) ("algo") with str2 ("rith").
    • The substring does not match str2. Move to the next index.
  5. Index 1 (i = 1):

    • Compare str1.substring(1, 5) ("lgor") with str2.
    • The substring does not match str2. Move to the next index.
  6. Continue Looping Until Index 4:

    • At each index, we are slicing str1 from the current index i to i + str2.length and comparing it with str2.
  7. Index 4 (i = 4):

    • At index 4, the substring of str1 is str1.substring(4, 8) ("rith").
    • This substring matches str2 exactly.
  8. Match Found:

    • Since the substring starting from index 4 matches str2, we return 4 as the index where str2 first occurs in str1.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

`

  • Time Complexity: , where n is the length of the str1 and m is the length of the str2. In the worst case, we need to check each substring of the str1 that has the same length as the str2.
  • Space Complexity: , as we only use a few variables for iteration and comparison, regardless of the input size.
Find the Index of the First Occurrence in a String (easy)
Merge Two Sorted Lists (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis